class ListNode(object):
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


def reverseList(head):
    """
    :type head: ListNode
    :rtype: ListNode
    """
    # 定义新的链表头部，指向原来的头部，这样头部移动的时候不至于原链表元素消失
    result = ListNode(0)
    result.next = head
    while head and head.next:
        # 例如 result->1->2->3 ==>result->2->1->3 其中1为r_next,2为h_next
        r_next = result.next
        h_next = head.next
        # result指向2
        result.next = h_next
        # 1指向3
        head.next = h_next.next
        # 2指向1
        h_next.next = r_next
    return result.next


node = ListNode(1)
node.next = ListNode(2)
node.next.next = ListNode(3)
node.next.next.next = ListNode(4)
node.next.next.next.next = ListNode(5)
node = reverseList(node)
print(node.val)
print(node.next.val)
print(node.next.next.val)
print(node.next.next.next.val)
print(node.next.next.next.next.val)
